package com.le.basic.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 设计RandomPool结构
 * 【题目】 设计一种结构，在该结构中有如下三个功能：
 *  1.insert(key)：将某个key加入到该结构，做到不重复加入。
 *  2.delete(key)：将原本在结构中的某个key移除。
 *  3.getRandom()： 等概率随机返回结构中的任何一个key。
 *  【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)
 */
public class Code_01_RandomPool {

    public static class Pool{
        private Map<String,Integer> keyIndexMap;  // key,size
        private Map<Integer,String> indexKeyMap; // size,key
        private Integer size;

        public Pool() {
            this.keyIndexMap = new HashMap<>();
            this.indexKeyMap = new HashMap<>();
            this.size = 0;
        }

        public void insert(String key){
            if (!this.keyIndexMap.containsKey(key)){
                this.keyIndexMap.put(key,this.size);
                this.indexKeyMap.put(this.size++,key);
            }
        }

        public void delete(String key){
            if (this.keyIndexMap.containsKey(key)){
                Integer deleteIndex = this.keyIndexMap.get(key);
                Integer lastIndex = --this.size;
                String lastValue = this.indexKeyMap.get(lastIndex);
                this.keyIndexMap.put(lastValue,deleteIndex);
                this.indexKeyMap.put(deleteIndex,lastValue);

                this.keyIndexMap.remove(key);
                this.indexKeyMap.remove(lastIndex);
            }
        }

        public String getRandom(){
            if (this.size == 0){
                return null;
            }
            int randomIndex = (int) (this.size * Math.random());
            return this.indexKeyMap.get(randomIndex);

        }

    }
    public static void main(String[] args) {
        Pool pool = new Pool();
        pool.insert("zuo");
        pool.insert("cheng");
        pool.insert("yun");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println();
        pool.delete("zuo");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
//        System.out.println(pool.getRandom());
//        System.out.println(pool.getRandom());


    }


}
